package com.jp.algorithm.sort;

public class MergeSort {

    public static void sort(int start, int end, int[] a){
        if(start == end)
            return;

        int mid=(end-start)/2 + start;

        sort(start,mid,a);
        sort(mid+1,end,a);

        int p1=start;
        int p2=mid+1;
        int[] tmpArray = new int[end-start+1];
        int i=0;
        while((p1!=mid+1) || (p2 !=end+1)){
            if(p1 == mid+1){
                tmpArray[i++]=a[p2];
                p2++;
                continue;
            }
            if(p2 == end+1){
                tmpArray[i++]=a[p1];
                p1++;
                continue;
            }
            if(a[p1]<a[p2]){
                tmpArray[i++]=a[p1];
                p1++;
            }else{
                tmpArray[i++]=a[p2];
                p2++;
            }
        }
        System.arraycopy(tmpArray,0,a,start,tmpArray.length);

    }

    public static  void print(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args) {
        int[] a={5,4,19,30,2,10,33,80};
        sort(0,a.length-1,a);
        print(a);
    }
}
